/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：HashQuad.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-04
Function List ：
Description   ：HashTable(Open addressing hashing)
******************************************************/

#include "HashQuad.h"
#include <stdlib.h>   // for malloc
#include <stdbool.h>  // for bool
#include <stdio.h>    // for printf
#include "FatalError.h"

#define MinTableSize (10)

typedef enum KindOfEntry {
    Legitimate = 0,
    Empty,
    Deleted,
} KindOfEntry;

struct HashEntry {
    ElementType Element;
    KindOfEntry Info;
};

typedef struct HashEntry Cell;

/* Cell *TheCells will be an array of */
/* HashEntry cells, allocated later */
struct HashTbl {
    int   TableSize;
    Cell *TheCells;
};

// Static Function Lists
static int NextPrime(int N);
static Index Hash(ElementType Key, int TableSize);

/* Return next prime; assume N >= MinTableSize */
static int NextPrime(int N) {
    int i;
    bool flag;

    if (N % 2 == 0) {
        N++;
    }

    for ( ; ; N += 2) {
        flag = true;
        for (i = 3; i * i <= N; i += 2) {
            /* Not prime! */
            if (N % i == 0) {
                flag = false;
                break;
            }
        }

        if (flag) {
            return N;
        }
    }
}

/* Hash function for ints */
Index Hash(ElementType Key, int TableSize) {
    return Key % TableSize;
}

HashTable InitializeTable(int TableSize) {
    HashTable H;
    int i;

    if (TableSize < MinTableSize) {
        Error("Table size is too small");
        return NULL;
    }

    /* Allocate table */
    H = (HashTable)malloc(sizeof(struct HashTbl));
    if (H == NULL) {
        FatalError("Out of space!!!");
    }

    H->TableSize = NextPrime(TableSize);

    /* Allocate array of Cells */
    H->TheCells = (Cell *)malloc(sizeof(Cell) * H->TableSize);
    if (H->TheCells == NULL) {
        FatalError("Out of space!!!");
    }

    for (i = 0; i < H->TableSize; ++i) {
        H->TheCells[i].Info = Empty;
    }

    return H;
}

void DestroyTable(HashTable H) {
    free(H->TheCells);
    free(H);
}

/* Mid-Square method */
Position Find(ElementType Key, HashTable H) {
    Position CurrentPos;
    int CollisionNum;

    CollisionNum = 0;
    CurrentPos = Hash(Key, H->TableSize);
    while (H->TheCells[CurrentPos].Info != Empty &&
           H->TheCells[CurrentPos].Element != Key) {
        /* Probably need strcmp!! */
        CurrentPos += 2 * ++CollisionNum - 1;
        if (CurrentPos >= H->TableSize) {
            CurrentPos -= H->TableSize;
        }
    }

    return CurrentPos;
}

void Insert(ElementType Key, HashTable H) {
    Position P;

    P = Find(Key, H);
    if (H->TheCells[P].Info != Legitimate) {
        /* OK to insert here */
        H->TheCells[P].Info = Legitimate;
        H->TheCells[P].Element = Key;  /* Probably need strcpy! */
    }
}

void Delete(ElementType Key, HashTable H) {
    Position P;

    P = Find(Key, H);
    /* Found it! */
    if (H->TheCells[P].Info == Legitimate) {
        H->TheCells[P].Info = Deleted;
    }
}

ElementType Retrieve(Position P, HashTable H) {
    return H->TheCells[P].Element;
}

HashTable Rehash(HashTable H) {
    int i;
    int OldSize;
    Cell *OldCells;

    OldCells = H->TheCells;
    OldSize  = H->TableSize;

    /* Get a new, empty table */
    H = InitializeTable(2 * OldSize);

    /* Scan through old table, reinserting into new */
    for (i = 0; i < OldSize; ++i) {
        if (OldCells[i].Info == Legitimate) {
            Insert(OldCells[i].Element, H);
        }
    }

    free(OldCells);

    return H;
}

void PrintHashTable(HashTable H) {
    int i;

    for (i = 0; i < H->TableSize; ++i) {
        if (H->TheCells[i].Info == Legitimate) {
            printf("%03d ", H->TheCells[i].Element);
        } else {
            printf("__ ");
        }
    }
    printf("\n");
}

// EOF

